/** 边信息（两个顶点的下标还有权值） */
export type KruskalEdge = {
    i: number, // 一条边的其中一个顶点的下标
    j: number, // 一条边的其中一个顶点的下标
    v: number, // 该边的权值
};

/** 顶点还没加到树之前不依赖于任何顶点 */
const NOT_VERTEX = -1;

/**
 * 克鲁斯卡尔(Kruskal)算法，求无向加权图的最小生成树。采用贪心算法思想，以加权边为主视角。
 * 最小生成树的特点：任意顶点之间只有一条路径（没有环），n个顶点的最小生成树有n-1条边（代价最小）。
 * 生活中例如为一群岛屿建桥，保证每个岛都在体系中，用代价最少的桥来连接它们。
 * @param graph 无向加权图（邻接矩阵）
 * 下面的代码有些可以利用技巧合并，但为了以后还查看时还读懂场景就不进行优化了
 */
export const kruskal = (graph: number[][]): KruskalEdge[] => {
    const edge: KruskalEdge[] = []; // 图的所有边
    const length = graph.length; // 图顶点的个数
    const dependency = []; // 最小生成树中顶点之间的依赖关系。查看getColor函数。

    // 遍历图，拿到所有边的信息（两个顶点的下标还有权值）
    for (let i = 0; i < length; i ++) {
        // 只用遍历图的一半即可（j永远小于i）
        for (let j = i + 1; j < length; j ++) {
            // 要是邻接的顶点才是边
            if (graph[i][j] > 0) {
                // 边的信息：两个顶点的下标还有权值
                edge.push({ i, j, v: graph[i][j] });
            }
        }
        // 初始化dependency，还没有生成树，全部置为-1  (NO_VERTEX)
        dependency.push(NOT_VERTEX);
    }

    // 对边的权值进行由小到大的排序
    edge.sort((a: KruskalEdge, b: KruskalEdge) => {
        return a.v - b.v;
    });

    const resultEdge: KruskalEdge[] = []; // 图最后生成的“最小生成树”

    // 图有n个顶点，那么它对应的最小生成树的边有n - 1个
    while (resultEdge.length < length - 1) {
        const current: KruskalEdge = edge.shift(); // 贪心点：一直取现存最小权值的边，直到满足最小生成树
        const i = current.i; // 这条边一个顶点 i
        const j = current.j; // 这条边另一个顶点 j
        const vertexI = getColor(dependency, i); // 顶点i依赖于谁
        const vertexJ = getColor(dependency, j); // 顶点j依赖于谁
        // 新加的边，其两个顶点都没有“依赖”，可以将这条边放入“最小生成树数组”中
        if (vertexI === NOT_VERTEX && vertexJ === NOT_VERTEX) {
            resultEdge.push(current);
            // 放入后，要为两个顶点指定一个“依赖”（默认置为i）
            dependency[i] = dependency[j] = i;
        }
        // 新加的边，两个顶点不互相“依赖”，可以将这条边放入“最小生成树数组”中
        else if (vertexI !== vertexJ) {
            resultEdge.push(current);

            // 新边的顶点i没有“依赖”，而顶点j有“依赖”
            if (vertexI === NOT_VERTEX) {
                // 那么放入后，将i的“依赖”置为j的“依赖”
                dependency[i] = vertexJ;
            }
            // 新边的顶点j没有“依赖”，但顶点i有“依赖”
            else if (vertexJ === NOT_VERTEX) {
                // 那么放入后，将j的“依赖”置为i的“依赖”
                dependency[j] = vertexI;
            }
            // 新边的顶点都有“依赖”且“依赖”不一样，新边将两段连在了一起
            else {
                // 连在一起后都只能依赖一个“依赖”。
                dependency[vertexI] = vertexJ;
            }
        } // 顶点i j“依赖”一样，新边不能加进来，会导致树生成环，而最小生成树是没有环的
    }
    return resultEdge;
};
/**
 * 查出目标顶点的颜色最终依赖谁
 * @param dependency 每个顶点的颜色关系（“依赖”）
 * @param index 目标顶点
 * 例如[-1, 2, 4, 3, 3]，给它下标依次命名A B C D E。
 * 可以看出A不依赖谁，也不在“最小生成树”中
 * B依赖于下标2也就是C，在“最小生成树”中
 * C依赖于下标4也就是E，在“最小生成树”中
 * E依赖于下标3也就是D，在“最小生成树”中
 * D最后指向自己，也就是说BC，CE，ED在“最小生成树”中是连在一起，
 * 他们最终的颜色决定于最后的D（D指向自己，不用管它到底啥颜色）
 * 最后加一个AD可以构成真正的最小生成树（这里暂时不讨论权值），并且这棵树的颜色决定于D
 */
const getColor = (dependency: number[], index: number): number => {
    // 目标顶点在最小生成树中，就遍历至它最终指向的点（最终的颜色标识）
    while (dependency[index] !== NOT_VERTEX) {
        // 指向自己（这段最终的颜色标识）
        if (dependency[index] === index) {
            return index;
        }
        // 指向其他顶点（这段共用一个颜色标识）
        index = dependency[index];
    }
    // 目标顶点不在最小生成树中，也就是它不指向谁
    return NOT_VERTEX;
};

